
// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
    // 反转链表
    ListNode *reverseList(ListNode *head)
    {
        // 一定是非空链表
        ListNode *pev = nullptr;
        ListNode *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = pev;
            pev = cur;
            cur = next;
        }
        return pev;
    }
    // 相加并构建答案链表
    ListNode *createNewList(ListNode *l1, ListNode *l2)
    {
        // 头节点
        ListNode *new_head = nullptr;
        // 进位
        int t = 0;
        // 高精度加法
        while (l1 || l2)
        {
            // 加法操作数
            int val_1 = 0;
            int val_2 = 0;
            if (l1)
                val_1 = l1->val;
            if (l2)
                val_2 = l2->val;
            // 合
            int sum = val_1 + val_2 + t;
            // 进位
            t = sum / 10;
            // 当前位
            int x = sum % 10;
            // 更新答案
            ListNode *new_node = new ListNode(x, nullptr);
            if (new_head == nullptr)
            {
                new_head = new_node;
            }
            else
            {
                // 头插
                new_node->next = new_head;
                new_head = new_node;
            };
            if (l1)
                l1 = l1->next;
            if (l2)
                l2 = l2->next;
        }
        // 处理剩余进位
        if (t)
        {
            ListNode *new_node = new ListNode(t, nullptr);
            // 头插
            new_node->next = new_head;
            new_head = new_node;
        }
        return new_head;
    }

public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        // 反转链表 + 高精度加法
        return createNewList(reverseList(l1), reverseList(l2));
    }
};
